Unlike conventional wireless networks, such as cellular networks, ad-hoc networks do not have an infrastructure. Typically, ad-hoc networks use a large number of low complexity transceivers (nodes) to communicate information. This decreases cost and sensitivity to failure of a single link. This makes ad-hoc networks candidates for applications that require ultra-reliable communications links.
Highly reliable ad-hoc wireless networks have two competing constraints. The energy consumption has to be low, because the nodes are typically battery operated, and exhausting the battery can lead to failure, and the probability for successful transmission of data should be high. That is, a message is to be transmitted from a source node to a destination node within a predetermined delay constraint. Smaller delays require more energy because higher power may be required to increase reliable reception.
In ad-hoc networks, it is desired to select a route, i.e., a sequence of nodes, which passes the message to the destination within the delay constraint, while minimizing energy consumption. A simple solution uses physical-layer transmission with a fixed message size and coding rate, selected so that that each link simply attempts to transmit a message within a fixed interval of time. Then, meeting the delay constraint is equivalent to limiting the number of hops.
However, this simple approach ignores the possibility of decreasing the overall delay by using more energy on certain links, and, possibly less on others. For a single link, the trade-off between transmission time and energy is straightforward. According to the Shannon's capacity equation, the possible data rate increases logarithmically with the transmit power. However, for networks with multiple hops, the trade-off becomes much more complicated. It involves selecting a route and then an energy level for each hop along the route.
Fountain Code
Fountain codes (also known as rateless erasure codes) are a class of erasure codes with the property that a potentially limitless sequence of encoding symbols can be generated from a given set of source symbols such that the original source symbols can be recovered from any subset of the encoding symbols of size equal to or only slightly larger than the number of source symbols.
The fountain code is optimal when the original k source symbols can be recovered from any k encoding symbols. Fountain codes have efficient encoding and decoding algorithms and that allow the recovery of the original k source symbols from any k′ of the encoding symbols with high probability, where k′ is just slightly larger than k.
Conventional methods for resource allocation for multi-hop fountain-coded transmissions are iterative, and each step has high polynomial computational complexity.
It is desired to minimize the total energy needed to propagate a message along a path of wireless links within a fixed time constraint, considering that following nodes are receiving fragments of previous fountain-coded transmissions.